﻿RAMIFICACION Y PODA  (Branch and Bound   B&B)

Se trata de una continuación natural del Método de Vuelta Atrás (Backtracking), y
por extensión de la Búsqueda en Profundidad y en Anchura, por lo que conviene
repasar esos temas pues parte de las ideas básicas del backtarcking, en especial la
generación de espacios de búsqueda tan reducidos como sea posible (evitando 
inútiles repeticiones, por ejemplo cuando el orden de los elementos en una solución
no importa), se han de aplicar del mismo modo.

El método básico es totalmente genérico, pero por ello mismo su utilización sin
tener en cuenta la especificidad de cada problema, resulta poco interesante.
Es muy importante, por tanto, ver bastantes ejemplos y sobre todo tener en cuenta
que el manejo de cotas excesivamente sencillas, tanto inferiores como superiores, 
puede no resultar demasiado meritorio. Sin embargo, también es habitual que el exceso 
de complicaciones al definir esas cotas nos pueda llevar al absurdo de perder más
tiempo en su cálculo que el que a la postre ahorraremos.

El método se suele aplicar en la resolución de problemas intrínsicamente 
difíciles (NP-completos), por lo que es habitual que no podamos hablar de 
soluciones "siempre buenas", aunque sí trataremos de dar con buenas heurísticas
que "prometan" comportarse bien en "muchos casos".

Dado ese carácter heurístico el "Método" ha dejado de aparecer en bastantes manuales
modernos de "Algorítmica" (e.g. Cormen et al. , Sedgewick) y en cambio sigue explicandose
en cursos de Investigación Operativa (cuyo problema de optimización lineal entera supuso
de hecho la primera presentación del Método) y en textos de Inteligencia Artificial, al
considerarse el tema de la búsqueda rápida de soluciones vía estrategias "inteligentes".

Por mi parte os recomiendo la lectura de:

  i) La breve presentación en el Brassard-Bratley (Fund. Algorítmica) Sección 9.7.
 ii)  Las secciones 6.1 y 6.2 del Neapolitan-Naimipour (Found. Algorithmics),
       aunque la segunda me parece innecesariamente larga.
iii) El Capítulo 8 del Horowithz, Sahni, Rajasekaran (Computer Algorithms),
       sólo si uno se quiere tragar casi 40 páginas bastante repetitivas.